﻿/*
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6
*/

#include "AllInc.h"

 struct ListNode 
 {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
 };
 
class Solution {
public:
	ListNode* mergeKLists(vector<ListNode*>& lists) 
	{
		ListNode result(0);

		priority_queue<pair<int, ListNode*>> record;
		while (!lists.empty())
		{
			if (record.empty())
			{
				for (size_t i = 0; i < lists.size(); i++)
				{
					if (lists[i])
					{
						record.push(make_pair(lists[i]->val, lists[i]));
						lists[i] = lists[i]->next;
					}
					else
					{
						lists.erase(lists.begin() + i);
					}
				}
			}
			else
			{
				result.next = record.top().second;
				record.pop();
				if (record.top().second->next)
				{
					record.push(make_pair(record.top().second->next->val, record.top().second->next));
				}
			}
		}

		return result.next;
	}
};
//int main()
//{
//	ListNode n1(1);
//	ListNode n2(4);
//	ListNode n3(5);
//	n1.next = &n2;
//	n2.next = &n3;
//
//	ListNode n4(1);
//	ListNode n5(3);
//	ListNode n6(4);
//	n4.next = &n5;
//	n5.next = &n6;
//
//	ListNode n7(2);
//	ListNode n8(6);
//	n7.next = &n8;
//
//	Solution s;
//	vector<ListNode*> data{&n1/*, &n4, &n7*/};
//	auto result = s.mergeKLists(data);
//
//	return 0;
//}